1062C - Banh-mi - CodeForces Solution

#include <bits/stdc++.h>
#define INF 1e18
#define MINSINF -1000000007
#define eps 1e-7
#define ff first
#define ss second
#define NN 10000000
#define pb(x) push_back(x)
#define pp() pop_back()
#define sq(a) a*a
#define MP(x,y) make_pair(x,y)
const int N=5e5+5;
const int mod=1e9+7;
typedef long long ll;
typedef long double ld;
using namespace std;
typedef pair <int,int> PII;
//memset(a, 0, sizeof(a));
//-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
//bool comp(pair<int,int>& a,pair<int,int>& b){
    //return a.ss<b.ss;
//}
//-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
ll power(ll a,ll b){
	ll res=1;
	while(b>0){
		if(b&1)  res=(res*a)%mod;
		a=(a*a)%mod;
		b/=2;
	}
	return res;
}
//-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
//ll inverse(ll a, ll p=mod){ return power(a,p-2); }
ll abso(ll a, ll b){    return ((a%mod)*(b%mod))%mod; }
//-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
//ll nCr(ll n, ll r){
    //vector <ll> fact(n+1,0); fact[0]=1;
    //for(ll i=1;i<=n;i++) fact[i]=abso(fact[i-1],i);
    //return abso(fact[n],abso(inverse(fact[n-r]),inverse(fact[r])));
//}
//-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
void solve(){
    int n,q;
    cin>>n>>q;
    string s;
    cin>>s;
    vector <int> pref(n+1,0);
    for(int i=0;i<n;i++){
        pref[i+1]=pref[i]+(s[i]-'0');
    }
    while(q--){
        int l,r;
        cin>>l>>r;
        if(pref[r]-pref[l-1]){
            ll sum=0;
            ll one=pref[r]-pref[l-1];
            ll zero=r-l+1-one;
            ll part_one=power(2,one)-1;
            sum+=abso(part_one,power(2,zero));
            cout<<sum<<endl;
        }
        else{
            cout<<0<<endl;
        }
    } 
}
int main(){	
    //freopen("file.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //clock_t tStart = clock();
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    //printf("Time taken: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
        
    return 0;
}
//-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
//a<<b means (a * pow(2,b))-> a * 2^b //left-sift operator <<
// checking set (i>>j)&1 or i&(1<<j)
//a>>b means (a / pow(2,b))-> a / 2^b //right-sift operator >>  
// __builtin_clz -> count the leading zeros of the integer from 32 bit
// __builtin_ctz -> count the trailing zeros of the given integer